import java.util.LinkedList;
import java.util.Queue;

public class TwoProngedTree {
    static class TreeNode{
        public char val ;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode node;
    public TreeNode createTree(){
        TreeNode node1=new TreeNode('A');
        TreeNode node2=new TreeNode('B');
        TreeNode node3=new TreeNode('C');
        TreeNode node4=new TreeNode('D');
        TreeNode node5=new TreeNode('E');
        TreeNode node6=new TreeNode('F');
        TreeNode node7=new TreeNode('G');
        node=node1;
        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;
        node3.right=node7;
        return  node;
    }
    //前序遍历
    public void  preOrder(TreeNode root){
        if (root==null){
            return;
        }
        System.out.print(root.val +" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍历
    public void inOrder(TreeNode root){
        if (root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val +" ");
        inOrder(root.right);
    }
    //后序遍历
    public void postOrder(TreeNode root){
        if(root==null){
            return;
        }
        preOrder(root.left);
        preOrder(root.right);
        System.out.print(root.val+" ");
    }
    public int size;
    public int traverseSize(TreeNode root){
        if (root==null){
            return 0;
        }
        size++;
        traverseSize(root.left);
        traverseSize(root.right);
        return size;
    }
    public int recursionSize(TreeNode root){
        if (root==null){
            return 0;
        }
        return recursionSize(root.left)+recursionSize(root.right)+1;
    }
    public int leafSize=0;
    public int getLeafNodeCount(TreeNode root){
        if (root==null){
            return 0;
        }
        if ( root.left==null&&root.right==null){
            leafSize++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return leafSize;
    }
    public int getLeafSize(TreeNode root){
        if (root==null){
            return 0;
        }
        if (root.left==null&&root.right==null)
        {
            return 1;
        }
            return getLeafSize(root.left)+getLeafSize(root.right);
    }
    public int getKLevel(TreeNode root,int k){
        if (root==null){
            return 0;
        }
        if (k==1){
            return 1;
        }
        return getKLevel(root.left,k-1)+getKLevel(root.right,k-1);
    }
    public int getHeight(TreeNode root){
        if (root==null){
            return 0;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return Math.max(leftHeight,rightHeight)+1;
    }
    public TreeNode contains(TreeNode root,char val){
        if (root==null){
            return null;
        }
        if (root.val==val){
            return root;
        }
        TreeNode ret=contains(root.left,val);
        if (ret!=null){
            return ret;
        }
        ret=contains(root.right,val);
        if (ret!=null){
            return ret;
        }
        return null;
    }
   
}

